class Solution {
public:
    void reverse(string& s, int beg, int end)
    {
        for (; beg <= end; ++beg, --end)
        {
            swap(s[beg], s[end]);
        }
    }
    void remove_extraspace(string& s)
    {
        unsigned int slow = 0;
        unsigned int fast = 0;
        while (s.size() > 0 && fast < s.size() && s[fast] == ' ')
            ++fast;
        for (; fast < s.size(); ++fast)
        {
            if (fast > 0 && s[fast - 1] == s[fast] && s[fast] == ' ')
                continue;
            else
                s[slow++] = s[fast];
        }
        if (s[slow - 1] == ' ')
            s.resize(slow - 1);
        else
            s.resize(slow);
    }
    string reverseWords(string s) {
        remove_extraspace(s);
        reverse(s, 0, s.size() - 1);
        int end = -2;
        int beg = 0;
        while ((end + 2) < s.size())
        {
            beg = end + 2;
            while ((end + 2) < (s.size() - 1) && s[end + 2] != ' ')
            {
                ++end;
            }
            if ((end + 2) == (s.size() - 1))
                end = end + 2;
            else
                end = end + 1;
            reverse(s, beg, end);
        }
        return s;
    }
};
